home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / std / c / 618 < prev    next >
Text File  |  1996-08-06  |  3KB  |  89 lines
  1. Newsgroups: comp.std.c
  2. Path: nntp.coast.net!torn!sq!msb
  3. From: msb@sq.com (Mark Brader)
  4. Subject: Re: Restrictions on qsort compare function?
  5. Message-ID: <1996Mar21.113301.2622@sq.com>
  6. Organization: SoftQuad Inc., Toronto, Canada
  7. References: <4iokop$h4p@lyra.csx.cam.ac.uk> <4iqjar$2m9@usenet.pa.dec.com>
  8. Date: Thu, 21 Mar 1996 11:33:01 GMT
  9.  
  10. > > Are there any limitations on what the sort function
  11.  
  12. It's better to call it a comparison function; qsort() is the sort function.
  13.  
  14. > > passed over to qsort can do or return?
  15.  
  16. The standard states
  17.  
  18. #  The function shall return an integer less than, equal to, or greater
  19. #  than zero if the first argument is considered to be respectively
  20. #  less than, equal to, or greater than the second.
  21.  
  22. In other words, it must yield an ordering of the possible data values.
  23. This is only the case if
  24.  
  25.     1. It is a pure function:
  26.        repeated calls to compar(x,y) yield a result having the
  27.            same sign each time
  28.  
  29.     2. It is antisymmetric (I think that's the right word):
  30.        if compar(x,y) <  0, then compar(y,x) >  0
  31.        if compar(x,y) == 0, then compar(y,x) == 0
  32.        if compar(x,y) >  0, then compar(y,x) <  0
  33.  
  34.     3. If is transitive:
  35.        if compar(x,y) > 0 && compar(y,z) > 0, then compar(x,z) > 0
  36.  
  37. > > I know it's meant to return < 0, 0 or > 0 for the various compare
  38. > > operations, but which you return is purely up to your own comparison
  39. > > system.
  40.  
  41. Yes, so long as it obeys *some* comparison system.
  42.  
  43. > > On tracking down a bug in some old code I noticed that we had the
  44. > > compare function returning something like "a > b" instead of "b - a".
  45. > 
  46. > Just one sentence earlier, you gave the exact reason why
  47. > it doesn't matter if you do "a > b" instead of "a - b".
  48.  
  49. Of course it matters.  With this function, if compar(x,y) > 0, then
  50. compar(y,x) == 0.  This is not antisymmetric.
  51. it is not a proper comparison function and the behavior is undefined.
  52.  
  53. > (Actually it can matter:  if "a - b" would overflow then doing "a > b"
  54. > will fix it instead of yielding undefined behavior :-)
  55.  
  56. Well, "a - b" is indeed unsuitable in general due to potential overflow.
  57. If the numbers being subtracted are floating-point or are signed integers,
  58. then arithmetic overflow may occur, causing undefined behavior.  It might
  59. be safe if they are unsigned integers, but then, unless they are narrower
  60. than int, you run into implementation-defined behavior on converting the
  61. result of the subtraction to the int that the function returns.
  62.  
  63. But changing to "a > b", as noted, does not fix it.  If simple arithmetic
  64. comparison is what you want, then you should use something like:
  65.  
  66.     (a > b)? 1: (a < b)? -1: 0
  67.  
  68. Terser equivalents, but probably considered less clear by most people, are:
  69.  
  70.     (a < b)? -1: (a > b)
  71. and
  72.     (a > b) - (a < b)
  73.  
  74. > > My understanding of this is that qsort() ought to be able to handle any
  75. > > [comparison] function, even if it's something as dumb as (rand()%3)-1.
  76. > 
  77. > That would not be a [comparison] function (it might even assert that a < b
  78. > and b < c and c < a).
  79.  
  80. Right.  In fact, it would not necessarily obey any of the three properties
  81. mentioned above, so the behavior of qsort() would be undefined.
  82.  
  83. -- 
  84. Mark Brader                 At any rate, C++ != C.  Actually, the value of the
  85. msb@sq.com                  expression "C++ != C" is [undefined].
  86. SoftQuad Inc., Toronto                                  -- Peter da Silva
  87.  
  88. My text in this article is in the public domain.
  89.